package leetcode215

import (
	"container/heap"
	"math"
)

func findKthLargest(nums []int, k int) int {
	if k == 0 {
		return 0
	}
	topK := make([]int, k+1)
	for i := range topK {
		topK[i] = math.MinInt32
	}
	for _, num := range nums {
		for i2 := 1; i2 <= k; i2++ {
			if topK[i2] < num {
				topK[i2-1] = topK[i2]
				topK[i2] = num
			}
		}
	}
	return topK[1]
}

func sortTopK(arr []int, k int) []int {
	arr = buildHeapify(arr)
	n := len(arr)
	for i := n; i >= 0; i-- {
		heap.Init()
	}
	return
}

func buildHeapify(arr []int) []int {
	n := len(arr)
	lastParentNode := (n - 1) / 2
	for i := lastParentNode; i >= 0; i-- {
		heapify(arr, n, i)
	}
	return arr
}

func heapify(arr []int, n, i int) []int {
	if i > n {
		return arr
	}
	left := i*2 + 1
	right := i*2 + 2
	max := i
	if left < n && arr[left] > arr[max] {
		max = left
	}

	if right < n && arr[right] > arr[max] {
		max = right
	}
	if max != i {
		arr[i], arr[max] = arr[max], arr[i]
		heapify(arr, n, max)
	}
	return arr
}
